package shelly.basic.class03;

import shelly.Util;
import shelly.common.DoubleNode;
import shelly.common.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Shelly
 * @create: 2023-01-26 09:16:49
 * @describe: 单链表反转、双链表反转
 */
public class Code01_ReverseList {
    // 单链表反转
    public static Node reverseLinkedList(Node head){
        Node pre = null;
        Node next = null;
        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    // 容器版单链表反转
    public static Node testReverseLinkedList(Node head){
        if (head == null) {
            return null;
        }
        ArrayList<Node> list = new ArrayList<>();
        while (head != null){
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int size = list.size();
        for (int i = 1;i< size;i++){
            list.get(i).next = list.get(i-1);
        }
        return list.get(size-1);
    }





    // for test 对数器
    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 10000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = Util.generateRandomLinkedList(len, value);
            List<Integer> list1 = Util.getLinkedListOriginOrder(node1);
            node1 = reverseLinkedList(node1);
            if (!Util.checkLinkedListReverse(list1, node1)) {
                System.out.println("===原链表=========");
                for (int j = 0;j< list1.size();j++){
                    System.out.print(list1.get(j) + " ");
                }
                System.out.println("===反转链表=========");
                while(node1 != null){
                    System.out.print(node1.value + " ");
                    node1 = node1.next;
                }
                System.out.println("Oops1!");
            }

			Node node2 = Util.generateRandomLinkedList(len, value);
			List<Integer> list2 = Util.getLinkedListOriginOrder(node2);
			node2 = testReverseLinkedList(node2);// 通过容器反转
			if (!Util.checkLinkedListReverse(list2, node2)) {
				System.out.println("Oops2!");
                System.out.println("===原链表=========");
                for (int j = 0;j< list2.size();j++){
                    System.out.print(list2.get(j) + " ");
                }
                System.out.println("===反转链表=========");
                while(node2 != null){
                    System.out.print(node2.value + " ");
                    node2 = node2.next;
                }
			}

			/*DoubleNode node3 = generateRandomDoubleList(len, value);
			List<Integer> list3 = getDoubleListOriginOrder(node3);
			node3 = reverseDoubleList(node3);
			if (!checkDoubleListReverse(list3, node3)) {
				System.out.println("Oops3!");
			}

			DoubleNode node4 = generateRandomDoubleList(len, value);
			List<Integer> list4 = getDoubleListOriginOrder(node4);
			node4 = reverseDoubleList(node4);
			if (!checkDoubleListReverse(list4, node4)) {
				System.out.println("Oops4!");
			}*/

        }
        System.out.println("test finish!");

    }
    /////////////////////////////双链表//////////////////////////////////////
    // 双链表反转
    public static DoubleNode reverseDoubleLinkedList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }



}
